package com.ztom.top100;

/**
 * 最长递增子序列
 * <p>
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 *
 * @author ZhangTao
 */
public class Code76LengthOfLIS {

    /**
     * dp: 以 i 位置结尾最长值, 找到dp[0, n - 1]的最大值即可
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            int curMax = 0;
            for (int j = 0; j < i; j++) {
                // 必须 i 位置的值大于前面的值
                if (nums[i] > nums[j]) {
                    // 找到前面位置的最大值
                    curMax = Math.max(curMax, dp[j]);
                }
            }
            // 必须选择 i 位置的值
            dp[i] = curMax + 1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /**
     * 贪心 + 二分法
     * 贪心: 要使上升子序列尽可能的长, 则需要让序列上升得尽可能慢, 即最后一个数尽可能小
     * 二分: 如果 nums[i] 小于 res[index],
     * 使用二分去 res 数组找到大于等于 nums[i] 的第一个位置 k,
     * 使 res[k] = nums[i]
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int[] res = new int[nums.length];
        // 记录 res 收集到的当前下标
        int index = -1;
        for (int i = 0; i < nums.length; i++) {
            // 直接收集
            if (index == -1 || nums[i] > res[index]) {
                res[++index] = nums[i];
                continue;
            }
            if (nums[i] <= res[index]) {
                // 二分查找到大于等于 nums[i] 的第一个位置
                int k = search(res, 0, index, nums[i]);
                res[k] = nums[i];
            }
        }
        return index + 1;
    }

    private int search(int[] nums, int l, int r, int t) {
        int mid = 0;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (nums[mid] >= t) {
                if (mid == 0 || nums[mid - 1] < t) {
                    return mid;
                }
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
}
